package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

import java.util.Arrays;
import java.util.Random;

/**
 * @author Dennis Li
 * @date 2020/9/8 16:25
 */
public class SortList_148 {

    public ListNode sortList(ListNode head) {
        // 判空返回, head为空或者下一位为空时都应该返回
        if (head == null || head.next == null) return head;

        // 找到中间结点，并进行链表的截断 -- 直到拆分成一个个的节点，再进行组合
        ListNode preMiddle = middleNode(head);
        ListNode rightHead = preMiddle.next;
        preMiddle.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        return merge(left, right);
    }

    // 找到中间结点前的一个结点
    private ListNode middleNode(ListNode head) {
        ListNode fast = head, slow = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow == null ? head : slow.next;
        }
        return slow;
    }

    // 合并两个有序链表
    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummy = new ListNode(-1), cur = dummy;

        while (left != null && right != null) {
            if (left.val > right.val) {
                cur.next = right;
                right = right.next;
            } else {
                cur.next = left;
                left = left.next;
            }
            cur = cur.next;
        }

        cur.next = left != null ? left : right;

        return dummy.next;
    }

    static class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            return sort(head);
        }

        private ListNode sort(ListNode head) {
            ListNode middle = middleNode(head);
            ListNode left = head, right = middle == null ? null : middle.next;
            if (middle != null) middle.next = null;
            left = sort(left);
            right = sort(right);
            return merge(left, right);
        }

        private ListNode middleNode(ListNode head) {
            // 返回中间结点的前一个结点
            ListNode fast = head, slow = null;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow == null ? head : slow.next;
            }
            return slow;
        }

        private ListNode merge(ListNode left, ListNode right) {
            if (left == null || right == null) return left != null ? left : right;

            if (left.val < right.val) {
                left.next = merge(left.next, right);
            } else {
                right.next = merge(left, right.next);
            }

            return left.val < right.val ? left : right;
        }

        private ListNode merge2(ListNode left, ListNode right) {
            ListNode dummy = new ListNode(Integer.MIN_VALUE), cur = dummy;

            while (left != null && right != null) {
                if (left.val < right.val) {
                    cur.next = left;
                    left = left.next;
                } else {
                    cur.next = right;
                    right = right.next;
                }
            }
            cur.next = left != null ? left : right;

            return dummy.next;
        }
    }
}
